package ljl.codetop300;

import java.util.Arrays;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的连续子数组
 * [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。
 * 如果不存在符合条件的子数组，返回 0
 *
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 示例 2：
 *
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 * 示例 3：
 *
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 *
 * 一看就是滑动窗口，没啥意思，能不能秒杀？
 */
public class _209_min_sub_array_len {

  /**
   * 我寄吧居然不太会写！
   * 气死我了！
   *
   * 后来还是蒙出来了，因为过于简单
   */
  static class question {

    public int minSubArrayLen(int target, int[] nums) {
      int cur = 0;
      int min = nums.length + 1;
      int start = 0;
      for (int i = 0; i < nums.length; i++) {
        cur += nums[i];
        while (cur >= target) {
          min = Math.min(i - start + 1, min);
          cur -= nums[start++];
        }
      }
      return min == nums.length + 1 ? 0 : min;
    }
  }

  /**
   * 前缀和；数字必须都是正数，不然二分就失效了
   */
  static class qian_zhui_he {

    public int minSubArrayLen(int target, int[] nums) {
      int n = nums.length;
      int[] sums = new int[n + 1];
      for (int i = 0; i < n; i++) {
        sums[i + 1] = nums[i] + sums[i];
      }
      int res = Integer.MAX_VALUE;
      for (int i = 0; i < n; i++) {
        int t = target + sums[i];
        int pos = Arrays.binarySearch(sums, t);
        if (pos < 0) {
          pos = -pos - 1;
        }
        if (pos <= n) {
          res = Math.min(res, pos - i);
        }
      }
      return res == Integer.MAX_VALUE ? 0 : res;
    }
  }
}
